Computer Memory and neoEUDs
Before delving into the fascinating/migrane-inducing world of EUPs, it would be good to know what they are first, and how they work. This page will explain both. How computers store information When a computer program wants to store data temporarily, it uses something called memory. For example, if a program needs to multiply a variable by 2 and set some other variable to the result, this is performed in memory. For most programming languages, assembly language code is also stored in memory; this code is generated based on the source code written in C or whatever, and is what the computer actually runs. Memory is divided into bytes, which is the smallest unit of memory that people typically work with directly. (That being said, there is one unit smaller, the bit, eight of which make up a byte. People don't usually deal directly with bits, because they are small and because of how addressing works, but it's not unheard of.) Each byte has a numerical address, typically written in hexadecimal notation. 0xAF2, for example, would be the 2802nd byte in memory. Anything a computer wants to store in memory is stored by choosing a memory location, allocating a sufficient amount of memory there for the thing in question, and then writing to that address. For example, let's say a program needs to store an integer which can theoretically take up four bytes. It would select four adjacent bytes in memory, and write the number to these four bytes. Even if the number happens to be 2 at present, if the programmer has said it could go high enough to need four bytes, then four bytes will be allocated for it. To refer to this number again, the computer would look at the address where it stored it. Everything, in the end, is referred to by its address, which ultimately is just a number. (Now, in a programming language like C, things are referred to by names instead. When the program is compiled, though, these names are turned into numbers.) There is one more concept that should be explained here, which is that of arrays, specifically multidimensional arrays. An array is a programming construct that allows multiple variables to be stored in a way that guarantees that they will be adjacent in memory. Additionally, they all use the same name with a numerical postfix. (Remember that names don't matter in assembly code. This name is no exception, and still gets turned into a number.) If I'm programming in C++ and have an array of one-byte numbers, called derp, then derp7 would refer to the eight number in the array. (Computers count from 0, not 1; derp0 is the first element of this array.) If I refer to derp7, it takes the address of the start of the array, and adds eight bytes. (If I were using two-byte numbers, it would add 16 bytes, and 32 if I was using four-byte numbers, etc.) There are even multidimensional arrays - arrays of arrays, if you will. They work the same way, adding to the base address based on the size of the elements and the number given. This is important to EUPs because the deaths table, our ticket into Starcraft's memory, is a multidimensional array. Specifically, it's a 227-by-12 array of four-byte integers; the first represents a player ID, and the second a unit ID. (The Marine is unit ID 0, for example, and the Infested Terran is ID 50.) Overflows EUPs, and for that matter regular EUDs, rely on Starcraft's deaths table. With both, the objective is to give a piece of Starcraft's code that uses the deaths table a unit ID or player ID higher than it expects. This is an example of something called an overflow. Let's say a program allocated space in memory for 20 two-byte numbers, and you told it to add 5 to element 7. (In C++ syntax, if the array was named overflowExample, this would be "overflowExample6 += 5;".) It takes the element number (6), multiplies it by the length of an element (2), adds that to the memory address of the start of the array, and adds 5 to whatever it finds there. Now, what if you used element 47 in the same way? (In C++, "overflowExample46 += 5;".) Well, exactly the same thing would happen. It would multiply the element ID (46) times the length of an element (2), add that to the array start location, and add 5 to whatever is there. But, this is outside the array. It could be, well, anything. You just poked some arbitrary thing and added 5 to it. Usually, this is a very bad idea. However, this is exactly what we intentionally do when using EUDs, including EUPs. See, most programs have a fairly consistent memory structure, and a significant part of Starcraft's has been mapped out. We know, for example, that 0x59CCB0 holds the health of the first unit in the game's memory, that 0x58A364 is the start of the deaths table, and many other things. If we use an overflow with the deaths table carefully, we'll know exactly what the resulting memory location will hold. The deaths table, as said earlier, is a 227-by-12 array of four-byte integers. When Starcraft does something with the deaths table, it needs a unit ID and a player ID. It takes the player ID, adds the unit ID times 12, multiplies the result by 4, adds that to the start of the deaths table (0x58A364), and then does whatever to that address. For example, you could have a trigger that uses the deaths condition with the Power Generator (unit ID 200) and Player 42 (player ID 41). The address it looks at is 4((200*12) + 41) + 0x58A364, or 0x58C988. (This is a silly example, because this address is actually still within the deaths table.) Nothing prevents you from using unit IDs that don't have units defined for them, of course, with the deaths condition. You could use Unit 3900 and player 200, for example. This gives you 4((3900*12) + 200) + 0x58A364, which happens to be the HP of the unit at index 1367. This is commonly done in mapping to, for example, check how much HP a hero unit has. There is an trigger to write to the deaths table, and it would seem that one could use that to write anywhere above it; unfortunately, it was patched to not write above the deaths table. Enter EUPs. We can place units with extended IDs using the mapping program SCMDraft. Usually, this just crashes the game. But a few don't, and by placing and killing these units, we can write to memory locations above the deaths table. The equation is exactly the same: 4(unitID*12 + playerID) + 0x58A364. Killing such an extended unit adds 1 to that location.